//Given an m x n integer matrix heightMap representing the height of each unit c
//ell in a 2D elevation map, return the volume of water it can trap after raining.
// 
//
// 
// Example 1: 
//
// 
//Input: heightMap = [[1,4,3,1,3,2],
//                    [3,2,1,3,2,4],
//                    [2,3,3,2,3,1]]
//                    [6,9,7,6,8,7]
//Output: 4
//Explanation: After the rain, water is trapped between the blocks.
//We have two small pounds 1 and 3 units trapped.
//The total volume of water trapped is 4.
// 
//
// Example 2: 
//
// 
//Input: heightMap = [[3,3,3,3,3],
//                    [3,2,2,2,3],
//                    [3,2,1,2,3],
//                    [3,2,2,2,3],
//                    [3,3,3,3,3]]
//                    [15,12,11,12,15]
//Output: 10
// 
//
// 
// Constraints: 
//
// 
// m == heightMap.length 
// n == heightMap[i].length 
// 1 <= m, n <= 200 
// 0 <= heightMap[i][j] <= 2 * 104 
// 
// Related Topics 堆 广度优先搜索 
// 👍 332 👎 0


package leetcode.editor.cn;

//Java：Trapping Rain Water II
class P407TrappingRainWaterIi {
    public static void main(String[] args) {
        Solution solution = new P407TrappingRainWaterIi().new Solution();
        System.out.println(solution.trapRainWater(new int[][]
                       {{12,13,1,12},
                        {13,4,13,12},
                        {13,8,10,12},
                        {12,13,12,12},
                        {13,13,13,13}}));
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[][] xleftMax;
        int[][] xrightMax;
        int[][] yleftMax;
        int[][] yrightMax;
        int rowLen;
        int colLen;

        public int trapRainWater(int[][] heightMap) {
            rowLen = heightMap.length;
            colLen = heightMap[0].length;
            xleftMax = new int[rowLen][colLen];
            xrightMax = new int[rowLen][colLen];
            yleftMax = new int[colLen][rowLen];
            yrightMax = new int[colLen][rowLen];
            trappingX(heightMap);
            trappingY(heightMap);
            int sum = 0;
            for (int i = 1; i < rowLen; i++) {
                for (int j = 1; j < colLen; j++) {
                    int xMin = Math.min(xleftMax[i][j], xrightMax[i][j]);
                    int yMin = Math.min(yleftMax[j][i], yrightMax[j][i]);
                    int min = Math.min(xMin, yMin);
                    if (min > heightMap[i][j]) {
                        sum += min - heightMap[i][j];
                    }
                }
            }
            return sum;
        }

        public void trappingX(int[][] heightMap) {
            for (int i = 0; i < rowLen; i++) {
                for (int j = 0; j < colLen; j++) {
                    if (j == 0) {
                        xleftMax[i][j] = heightMap[i][j];
                    }else{
                        xleftMax[i][j] = Math.max(xleftMax[i][j - 1], heightMap[i][j]);
                    }
                }
            }
            for (int i = 0; i < rowLen; i++) {
                for (int j = colLen - 1; j >= 0; j--) {
                    if (j == colLen - 1) {
                        xrightMax[i][j] = heightMap[i][j];
                    }else{
                        xrightMax[i][j] = Math.max(xrightMax[i][j + 1], heightMap[i][j]);
                    }
                }
            }
        }

        public void trappingY(int[][] heightMap) {
            for (int i = 0; i < colLen; i++) {
                for (int j = 0; j < rowLen; j++) {
                    if (j == 0) {
                        yleftMax[i][j] = heightMap[j][i];
                    }else {
                        yleftMax[i][j] = Math.max(yleftMax[i][j - 1], heightMap[j][i]);
                    }
                }
            }
            for (int i = colLen - 1; i >= 0; i--) {
                for (int j = rowLen - 1; j >= 0; j--) {
                    if (j ==  rowLen - 1) {
                        yrightMax[i][j] = heightMap[j][i];
                    }else{
                        yrightMax[i][j] = Math.max(yrightMax[i][j + 1], heightMap[j][i]);
                    }
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}